public class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        sort(nums,0,nums.length-1,nums.length-k+1);
        return nums[nums.length-k];
    }

    private void sort(int[] nums, int start, int end, int threshold) {
        if (start==end){
            return;
        }
        int l=start,r=end;
        int mid=nums[(l+r)/2];
        while (l<=r){
            while (nums[l]<mid){
                l++;
            }
            while (nums[r]>mid){
                r--;
            }
            if (l<=r){
                int t=nums[l];
                nums[l]=nums[r];
                nums[r]=t;
                l++;
                r--;
            }
        }
        if (l-start>=threshold){
            sort(nums,start,l-1,threshold);
        }else{
            sort(nums,l,end,threshold-(l-start));
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution215().findKthLargest(new int[]{5,2,4,1,3,6,0},4));
    }
}
